Fila de prioridade

Fila de prioridade é uma estrutura de dados que armazena elementos com base em suas prioridades. Cada elemento possui uma prioridade associada a ele e a fila garante que os elementos com maior prioridade sejam atendidos primeiro.

As filas de prioridade podem ser implementadas de várias maneiras, como por meio de uma heap binária, uma árvore de busca binária balanceada ou uma lista ordenada.

Essa estrutura de dados é amplamente utilizada em algoritmos de otimização e em sistemas em que é necessário processar tarefas em ordem de prioridade.

Aplicações

Uma fila de prioridade é uma estrutura de dados muito útil para lidar com tarefas em que uma ordem de prioridade deve ser respeitada. Alguns exemplos de aplicação de fila de prioridade são:

1. Algoritmos de busca: em muitos algoritmos de busca, como A*, Dijkstra e Algoritmo de Bellman-Ford, é importante manter uma fila de prioridade para explorar os nós mais promissores primeiro.
2. Sistemas de atendimento: em sistemas de atendimento, como filas de espera em hospitais, bancos ou serviços de suporte, é comum usar uma fila de prioridade para lidar com pacientes ou clientes de acordo com sua gravidade ou urgência.
3. Escalonamento de processos: em sistemas operacionais, uma fila de prioridade é frequentemente usada para decidir qual processo deve ser executado em seguida, levando em consideração fatores como prioridade, tempo de espera e recursos disponíveis.
4. Codificação de Huffman: na codificação de Huffman, uma fila de prioridade é usada para construir a árvore de Huffman, que é uma árvore binária usada para codificar dados de forma eficiente.
5. Compressão de dados: em algoritmos de compressão de dados, como o algoritmo LZ77, uma fila de prioridade é usada para localizar o maior padrão de correspondência em uma string de dados.

Exemplo de código fonte

import java.util.PriorityQueue;

public class ExemploFilaPrioridade {

    public static void main(String[] args) {
        // Criação da fila de prioridade com capacidade inicial 10 e ordem natural de elementos
        PriorityQueue<Integer> fila = new PriorityQueue<>(10);

        // Adição de elementos na fila
        fila.add(7);
        fila.add(1);
        fila.add(4);
        fila.add(2);
        fila.add(9);
        fila.add(8);
        fila.add(3);
        fila.add(6);
        fila.add(5);

        // Impressão da fila
        System.out.println("Fila de prioridade: " + fila);

        // Remoção do elemento de maior prioridade
        int elementoRemovido = fila.poll();
        System.out.println("Elemento removido: " + elementoRemovido);

        // Impressão da fila após remoção
        System.out.println("Fila de prioridade após remoção: " + fila);

        // Verificação do elemento de maior prioridade sem removê-lo
        int maiorPrioridade = fila.peek();
        System.out.println("Elemento de maior prioridade: " + maiorPrioridade);
    }

}

Nesse exemplo, foi criado uma fila de prioridade de capacidade inicial 10 e ordem natural de elementos (menor para o maior). Em seguida, adicionamos vários elementos à fila e imprimimos a fila completa. Depois, removemos o elemento de maior prioridade (menor valor) da fila e imprimimos a fila novamente. Por fim, verificamos o elemento de maior prioridade sem removê-lo da fila.

Ver também

• Lista de termos relacionados aos algoritmos e estruturas de dados
• Escalonamento de processos
• Autómato
• Árvore (estrutura de dados)